package company.dynamic;

import com.company.tree.TreeNode;

import java.util.*;

/**
 * 337. 打家劫舍 III(树形dp)
 * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
 * <p>
 * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * <p>
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 
 * <p>
 * 输入: root = [3,2,3,null,3,null,1]
 * 输出: 7
 * 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
 * <p>
 * 输入: root = [3,4,5,1,3,null,1]
 * 输出: 9
 * 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
 * <p>
 * <p>
 * 分析：
 * 简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。
 * <p>
 * 1、对于每个节点来说,有选择和不被选择的可能，设置选择用f表示，不被选择用g表示
 * 2、当前节点为o，对于o，当选择了o，那么o的左右子节点l,r则不能被选择
 * 3、用f(o) 表示选择o节点时候，o节点的子树节点被选择的节点的最大权值和；g(o)表示不选择
 * o节点下，o节点的子树的节点被选择的节点的最大权值和； l r表示左右孩子节点
 * 4、当o被选择时候，o节点的孩子节点不能被选择，故o被选中情况下子树上被选择中点的最大权值=l和r不被选择中的最大权值相加
 * f(o) = g(l)+g(r)
 * 当o不被选中时候，o的孩子可以被选中，也可以不被选中。对于o的孩子x，对于o的贡献是x被选中和不被选中的较大值
 * g(o) =max(f(l),g(l))+max(f(r)，g(r))
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/house-robber-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Rob337 {
    static Map<TreeNode, Integer> f = new HashMap<>();
    static Map<TreeNode, Integer> g = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String[] treeNodes = input.replace("[", "").replace("]", "").replace(" ", "").split(",");
        Deque<TreeNode> deque = new LinkedList<>();
        int index = 0;
        TreeNode treeNode = new TreeNode(Integer.parseInt(treeNodes[0]));
        deque.offer(treeNode);
        while (++index < treeNodes.length) {
            TreeNode poll = deque.poll();
            if (!"null".equals(treeNodes[index])) {
                TreeNode left = new TreeNode(Integer.parseInt(treeNodes[index]));
                poll.setLeft(left);
                deque.offer(left);
            }

            ++index;
            if (index < treeNodes.length && !"null".equals(treeNodes[index])) {
                TreeNode right = new TreeNode(Integer.parseInt(treeNodes[index]));
                poll.setRight(right);
                deque.offer(right);
            }
        }
        System.out.println(rob(treeNode));
    }

    public static int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0),
                g.getOrDefault(root, 0));
    }

    // 后序遍历
    public static void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        dfs(node.getLeft());
        dfs(node.getRight());
        f.put(node, node.getValue() + g.getOrDefault(node.getLeft(),
                0) + g.getOrDefault(node.getRight(), 0));
        g.put(node, Math.max(f.getOrDefault(node.getLeft(),
                0), g.getOrDefault(node.getLeft(), 0))
                + Math.max(f.getOrDefault(node.getRight(), 0), g.getOrDefault(node.getRight(), 0)));
    }
}
